`
https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  const res = []
  const q = [root]

  // 正常的层序遍历
  while (q.length) {
    const node = q.shift()
    if (node === null) {
      res.push('#')
      continue
    }

    res.push(`${node.val}`)

    // 空指针也需要记录
    q.push(node.left)
    q.push(node.right)
  }

  return res.join(',')
};

/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data) {
  if (data[0] === '#') return null

  // 获取存储每个结点值的列表
  const nodes = data.split(',')

  // 根元素就是第一个元素
  const root = new TreeNode(+nodes[0])
  const q = [root]

  // index 变量记录正在序列化的节点在数组中的位置
  let index = 1
  // 思路类似于记录深度的层序遍历，每次只生成当前一层
  while (q.length) {
    const sz = q.length
    for (let i = 0; i < sz; i++) {
      const node = q.shift()
      // 为该结点构建左子结点
      const left = nodes[index++]
      if (left !== '#') {
        node.left = new TreeNode(+left)
        q.push(node.left)
      }
      // 为该结点构建右子结点
      const right = nodes[index++]
      if (right !== '#') {
        node.right = new TreeNode(+right)
        q.push(node.right)
      }
    }
  }

  return root
};

/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/